//
//  1137. 第 N 个泰波那契数.swift
//  手撕
//
//  Created by xiaoZuDeMeng on 2024/2/25.
//

import Foundation

//https://leetcode.cn/problems/n-th-tribonacci-number/description/
//泰波那契序列 Tn 定义如下：
//
//T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
//
//给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
//
//
//
//示例 1：
//
//输入：n = 4
//输出：4
//解释：
//T_3 = 0 + 1 + 1 = 2
//T_4 = 1 + 1 + 2 = 4
//示例 2：
//
//输入：n = 25
//输出：1389537
//
//
//提示：
//
//0 <= n <= 37
//答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

func 第N个泰波那契数(_ n: Int) -> Int {
    if n == 0 { return 0 }
    if n == 1 || n == 2 { return 1 }
    // cur用来记数。
    var cur = 2
    var F = 0
    var S = 1
    var T = 1
    var R = 0
    while cur != n {
        R = F + S + T
        // Swift 可以写成 (F,S,T) = (S,T,R)
        F = S
        S = T
        T = R
        cur += 1
    }
    return R
}

func 第N个泰波那契数1(_ n: Int) -> Int {
    var t: [Int] = Array(repeating: 0, count: n + 1)
    t[0] = 0
    if t.count >= 3 {
        t[1] = 1
        t[2] = 1
    } else if t.count >= 2 {
        t[1] = 1
    }
    if n >= 3 {
        for i in 3...n {
            t[i] = t[i - 1] + t[i - 2] + t[i - 3]
        }
    }
    return t[n]
}
